package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author Yi Jun jie
 * @Date 2021/3/2 22:11
 * 110. 平衡二叉树
 */
public class LeetCode110 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
        System.out.println(new Solution110().isBalancedPlus(treeNode));
    }
}

//用递归解决 (我自己的解决方式，这里效率不够高)
class Solution110 {

    static int maxSize = 100;

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        TreeNode T = root;
        TreeNode r;
        //这里可以使用一个层次遍历来遍历树 (这里的队列可以用一个数组)
        Queue<TreeNode> queue = new LinkedList<>();
        int front = 0, rear = 0;
        queue.offer(T);
        rear++;
        while (rear > front) {
            r = queue.poll();
            front++;
            if (Math.abs(treeDepth(r.left) - treeDepth(r.right)) > 1) return false;
            if (r.left != null) {
                queue.offer(r.left);
                rear++;
            }
            if (r.right != null) {
                queue.offer(r.right);
                rear++;
            }
        }
        return true;
    }

    // 这里效率不是很高不建议使用
    public boolean isBalancedPlus(TreeNode root) {
        if (root == null) return true;
        int front = 0, rear = 0;
        TreeNode[] que = new TreeNode[maxSize]; //定义一个队列，用于记录每一层的节点
        TreeNode q; // 用于保存节点地址的变量，相当于一个中转站
        rear = (rear + 1) % maxSize;//根节点入队
        que[rear] = root;
        while (front != rear) //当队列不空时，进行循环
        {
            front = (front + 1) % maxSize;
            q = que[front];  //出队
            System.out.println(q.val);
            if (q.left != null) //左子树不空，则左子树根节点入队
            {
                rear = (rear + 1) % maxSize;
                que[rear] = q.left;
            }
            if (q.right != null) //柚子树不空，则其根节点入队
            {
                rear = (rear + 1) % maxSize;
                que[rear] = q.right;
            }
        }
        return true;
    }

    //这里的递归思想值得借鉴
    public boolean isBalancedPlusPlus(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(treeDepth(root.left) - treeDepth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    //求树的深度
    int treeDepth(TreeNode T) {
        if (T == null) return 0;
        int left = treeDepth(T.left);
        int right = treeDepth(T.right);
        return (left > right ? left : right) + 1;
    }
}

//网上的优秀解法
class Solution110Plus {
    //主要区别就在这里，这里使用的是递归的思想
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
        }
    }

    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(height(root.left), height(root.right)) + 1;
        }
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}